
public class MyLinkList implements IList{
    //内部类
    class Node{
        public int val;
        Node next;
        public Node(int val){
            this.val=val;
        }
    }
    public Node head;
    public void create(){
        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        node1.next=node2;
        node2.next=node3;
       head= node1;
    }
    //头插法
    @Override
    public void addFirst(int data) {
        Node node=new Node(data);
        node.next=head;
        head=node;
    }
    //尾插法
    @Override
    public void addLast(int data) {
    Node node=new Node(data);
    Node end=head;
    while (end.next!=null){
        end=end.next;
    }
    end.next=node;
    }
    //在某一个位置
    @Override
    public void addIndex(int index, int data) {
    if(index<0||index>size()){
        System.out.println("位置不合法");
        return;
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==size()){
        addLast(data);
        return;
    }
    Node node=new Node(data);
    Node pre=getNode(index);
    node.next=pre.next;
    pre.next=node;
    }
    public Node getNode(int index){
        Node node=head;
        while (index-1!=0){
            node=node.next;
            index--;
        }
        return node;
    }

    @Override
    public boolean contains(int key) {
        Node node=head;
        while (node!=null){
            if(node.val==key){
                return true;
            }
            node=node.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
    if(head.val==key){
        head=head.next;
        return;
    }
    int index=getindex(key);
    Node node=head;

    while (index-1!=0){
        node=node.next;
        index--;
    }
    node.next=node.next.next;
    }
    public int getindex(int key){
        int count=0;
        Node node=head;
        while (node!=null){
            if(node.val==key){
                return count;
            }
            node=node.next;
            count++;
        }
        return -1;
    }

    @Override
    public void removeAllKey(int key) {
    if (head==null){
        return;
    }
    Node node=head;
    Node cur=head.next;
    while (cur!=null){
        if(cur.val==key){
            node.next=cur.next;
            cur=cur.next;
        }else {
            node=node.next;
            cur=cur.next;
        }
    }
    if(head.val==key){
        head=head.next;
    }
    }
    //求size
    @Override
    public int size() {
        Node node=head;
        int count=0;
        while (node!=null){
           count++;
            node=node.next;
        }
        return count;
    }
    //清空
    @Override
    public void clear() {
    Node node=head;
    while (node!=null){
        Node next=node.next;
        node.next=null;
        node=next;
    }
    head=null;
    }
    //遍历
    @Override
    public void display() {
        Node node=head;
        while (node!=null){
            System.out.print(node.val+" ");
            node=node.next;
        }

    }
    //反转链表
    public Node reverseList() {
        if(head==null||head.next==null){
            return head;
        }
        Node cur=head.next;
        head.next=null;
        while (cur!=null){
            Node curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
    //返回中间结点(传统方法)
    public Node middleNode() {
        if(head==null||head.next==null){
            return head;
        }
        int Size=size();
        int middle=Size/2;
       Node node=head;
        for (int i=0;i<middle;i++){
            node=node.next;
        }
        return node;
    }
    //返回中间结点(快、慢)
    public Node middleNode2() {
        Node fast=head;
        Node slow=head;
        while (fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //返回倒数第K个结点
    public Node FindKthToTail (int k) {
        Node fast=head;
        Node slow=head;
    if(k<=0||head==null){
        return null;
    }
    while (k-1>0){
        fast=fast.next;
        k--;
    }
    while (fast.next!=null){
        fast=fast.next;
        slow=slow.next;
    }
    return slow;

    }
    //合并两个升序链表
    public Node mergeTwoLists(Node list1, Node list2) {
        Node phead=new Node(-1);
        Node node=phead;
        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                node.next=list1;
                list1=list1.next;
            }else {
                node.next=list2;
                list2=list2.next;
            }
            node=node.next;
        }
        if (list1!=null){
            node.next=list1;

        }
        if(list2!=null){
            node.next=list2;

        }
        return phead.next;
    }
    //链表分割
    public Node partition(int x) {
        if (head==null){
            return null;
        }
        Node as=null;
        Node ae=null;
        Node bs=null;
        Node be=null;
        Node cur=head;
        while (cur!=null){
            if (cur.val<x){
              if(as==null){
                  //插入第一个节点
                  as=cur;
                  ae=cur;
                  cur=cur.next;
              } else {
                  ae.next=cur;
                  ae=ae.next;
                  cur=cur.next;
              }
            }else {
             //cur.val>x
             if(bs==null){
                 bs=cur;
                 be=cur;
                 cur=cur.next;
             }  else {
                 be.next=cur;
                 be=be.next;
                 cur=cur.next;
             }
            }
        }
        if(as==null){
            return bs;
        }
        ae.next=bs;
        if(bs != null) {
            //第2个区间有数据
            be.next = null;
        }
        head=as;
        return head;
    }
    //是否回文
    public boolean chkPalindrome() {
        //按照中间位置翻转链表
        //1.找到中间位置
        Node middle=middleNode2();
        //2.翻转
        Node ehead=middle;
        Node cur=ehead.next;
        while (cur!=null){
            Node curNext=cur.next;
            cur.next=ehead;
            ehead=cur;
            cur=curNext;

        }
        //从两头开始遍历
        Node snode=head;
        Node enode=ehead;
        while (snode!=enode||snode.next!=null){
//            if (snode.val!=enode.val){
//                return false;
//            }
//            if (snode.next==enode){
//                return true;
//            }
//                snode=snode.next;
//                enode=enode.next;
            if(snode.val==enode.val){
                snode=snode.next;
                enode=enode.next;
            }else {
                return false;
            }
        }
        return true;
    }

}
